"""
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import List
def ts(s):
    data = ""
    for key, value in s.items():
        if callable(value):
            continue
        if isinstance(value, int):
            data = "{}={}\t".format(key, value) + data
        else:
            data += "{}={}\t".format(key, value)
    print(data)

class Solution:
    """
    回溯的时候不选后面
    """

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []

        def backtrack(combination: List[int], res: int, start: int):
            """
            combination 存放回溯的列表
            res 存放target - 依次回溯的结果，用来判断是否相等，同样也可以用加法做
            start: 我感觉叫深度比较合适
            还能优化么？目前没想到
            """
            if res == 0:
                ans.append(combination)
                return
            for i in range(start, length):
                # print(candidates[start: length],"start=", start, "i=",i, "res=",res)
                ts(locals())
                if i> start and  candidates[i] == candidates[i-1]:
                    print("i=", i, "start=",start)
                    continue
                if candidates[i] > res:
                    break
                backtrack(combination + [candidates[i]],
                          res - candidates[i], i+1)

        length = len(candidates)
        if length != 0:
            candidates.sort()
            backtrack([], target, 0)
        return ans


if __name__ == "__main__":
    # res = Solution().combinationSum2([10, 1, 2, 7, 6, 1, 5], 8)
    # print(res)
    res = Solution().combinationSum2([2, 5, 2, 1, 2], 5)
    print(res)
    # res = Solution().combinationSum2([10, 1, 1, 5, 5, 2, 7, 6, 1, 5], 3)
    # print(res)
